- Размещение
-
В комбинаторике размещением называется расположение «предметов» (объектов) на некоторых «местах» при условии, что каждое место занято в точности одним предметом и все предметы различны. Более формально, размеще́нием (из n по k) называется упорядоченный набор из k различных элементов из некоторого множества различных же n элементов.
Пример 1: — это 4-х элементное размещение из 6-ти элементного множества .
Пример 2: некоторые размещения элементов множества по 2: ... ... ...
В отличие от сочетаний, размещения учитывают порядок следования предметов. Так, например, наборы и являются различными, хотя состоят из одних и тех же элементов (то есть совпадают как сочетания).
Содержание
Количество размещений
Количество размещений из n по k, обозначаемое , равно убывающему факториалу:
Последнее выражение имеет естественную комбинаторную интерпретацию: каждое размещение из n по k однозначно соответствует некоторому сочетанию из n по k и некоторой перестановке элементов этого сочетания; число сочетаний из n по k равно биномиальному коэффициенту , в то время как перестановок на k элементах ровно k! штук.
При k=n количество размещений равно количеству перестановок порядка n:[1][2][3]
Размещение с повторениями
Размещение с повторениями или выборка с возвращением[4] — это размещение «предметов» в предположении, что каждый «предмет» может участвовать в размещении несколько раз.
Количество размещений с повторениями
По правилу умножения количество размещений с повторениями из n по k, обозначаемое , равно:[5][1][4]
Например, количество вариантов 3-значного кода, в котором каждый знак является цифрой от 0 до 9 и может повторяться, равно:
См. также
Ссылки
- ↑ 1 2 Виленкин Н.Я. Глава III. Комбинаторика кортежей и множеств. Размещения с повторениями // Популярная комбинаторика. — М.: Наука, 1975. — С. 80. — 208 с.
- ↑ Теория конфигураций и теория перечислений
- ↑ Глава 3. Элементы комбинаторики. // Лекции по теории вероятностей.
- ↑ 1 2 Корн Г., Корн Т. Табл. 18.7-2(2.b), 18.7-3(2.b) // Справочник по математике для научных работников и инженеров. — М.: Наука, 1973. — С. 568. — 832 с.
- ↑ Комбинаторный анализ // Математическая энциклопедия / Под ред. И. М. Виноградова. — М., 1977. — Т. 2. — С. 974. — (Сов. энциклопедия).
Категория:- Комбинаторика
Wikimedia Foundation. 2010.